import time
import ctypes
import numpy as np
import matplotlib.pyplot as plt
from ctypes import c_int, c_ulonglong
from scipy.interpolate import CubicSpline
from concurrent.futures import ProcessPoolExecutor

# 加载共享库
slow_sort = ctypes.CDLL('./LibSlowSort.dll')
fast_sort = ctypes.CDLL('./LibFastSort.dll')

# 定义函数原型
slow_sort.bubble_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
slow_sort.opt_bubble_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
slow_sort.selection_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
slow_sort.insertion_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
slow_sort.bin_insertion_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]

fast_sort.heap_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
fast_sort.shell_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
fast_sort.quick_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]
fast_sort.merge_sort_int.argtypes = [np.ctypeslib.ndpointer(dtype=np.int32), c_ulonglong]


# 定义Python中的排序函数
def bubble_sort(arr):
    slow_sort.bubble_sort_int(arr, len(arr))


def opt_bubble_sort(arr):
    slow_sort.opt_bubble_sort_int(arr, len(arr))


def select_sort(arr):
    slow_sort.selection_sort_int(arr, len(arr))


def insert_sort(arr):
    slow_sort.insertion_sort_int(arr, len(arr))


def bin_insert_sort(arr):
    slow_sort.bin_insertion_sort_int(arr, len(arr))


def heap_sort(arr):
    fast_sort.heap_sort_int(arr, len(arr))


def shell_sort(arr):
    fast_sort.shell_sort_int(arr, len(arr))


def quick_sort(arr):
    fast_sort.quick_sort_int(arr, len(arr))


def merge_sort(arr):
    fast_sort.merge_sort_int(arr, len(arr))


# 测量排序算法运行时间的函数
def measure_sort_time(sort_func, arr):
    try:
        start = time.time()
        sort_func(arr)
        return time.time() - start
    except Exception as e:
        print(f"Sorting error: {e}")
        return None


# 并行计算平均用时
def compute_avg_times(sizes, sort_func, rand_arrays, iterations):
    times = np.zeros(len(sizes))

    with ProcessPoolExecutor() as executor:
        for i, size in enumerate(sizes):
            total_time = 0

            # 显示进度
            if i % 5 == 0:
                progress = ((i + 1) / len(sizes)) ** 3 * 100
                print(f"{sort_func.__name__}: {progress:05.2f}%...")

            # 提交并行任务
            tasks = [executor.submit(measure_sort_time, sort_func, arr.copy()) for arr in
                     [rand_arrays[size]] * iterations]

            # 收集结果
            for future in tasks:
                try:
                    total_time += future.result() or 0
                except Exception as e:
                    print(f"Error: {e}")

            times[i] = total_time / iterations

    print(f"{sort_func.__name__}: 100.00%...")
    return times


# 绘制排序时间图
def plot_sort_times(sizes, times_dict):
    plt.figure(figsize=(10, 6))

    for label, times in times_dict.items():
        cs = CubicSpline(sizes, times)
        x_new = np.linspace(sizes[0], sizes[-1], 1000)
        y_smooth = cs(x_new)
        plt.plot(x_new, y_smooth, label=label)

    plt.xlabel('Array Size')
    plt.ylabel('Average Time (seconds)')
    plt.legend()
    plt.grid(True)
    plt.xticks(np.linspace(sizes[0], sizes[-1], 10, dtype=int))
    plt.yticks(np.linspace(min(times.min() for times in times_dict.values()),
                           max(times.max() for times in times_dict.values()), 15))
    plt.show()


# 生成随机数组
def generate_arrays(sizes, rand_min, rand_max):
    return {size: np.random.randint(rand_min, rand_max, size=size) for size in sizes}


# 计算排序算法评分
def compute_scores(sizes, times_dict):
    def trapezoidal(x, y):
        n = len(x)
        integral = 0.0
        for i in range(1, n):
            h = x[i] - x[i - 1]
            integral += 0.5 * h * (y[i] + y[i - 1])
        return integral

    total_times = {label: trapezoidal(times, sizes) for label, times in times_dict.items()}
    min_total_time = min(total_times.values())
    scores = {label: 750 * (min_total_time / total_time) for label, total_time in total_times.items()}
    return sorted(scores.items(), key=lambda item: item[1], reverse=True)


# 比较排序算法
def compare_sorting_algorithms(min_size, max_size, num_divs, sort_funcs, rand_min=0, rand_max=int(1e5), iterations=6):
    sizes = np.linspace(min_size, max_size, num_divs, dtype=int)
    rand_arrays = generate_arrays(sizes, rand_min, rand_max)

    times_dict = {}
    start_time = time.time()
    for label, sort_func in sort_funcs.items():
        times_dict[label] = compute_avg_times(sizes, sort_func, rand_arrays, iterations)

    scores = compute_scores(sizes, times_dict)
    exec_time = time.time() - start_time

    import os
    os.system('cls' if os.name == 'nt' else 'clear')

    print("\n".join(f"{label}: {score:.2f}" for label, score in scores))
    print(f"Executed in {exec_time:.4f} seconds")

    plot_sort_times(sizes, times_dict)


# 测试函数
def test_slow_sorts():
    slow_sorts = {
        "Bubble": bubble_sort,
        "Opt Bubble": opt_bubble_sort,
        "Selection": select_sort,
        "Insertion": insert_sort,
        "Bin Insert": bin_insert_sort
    }
    # 数据最小长度，最大长度，划分次数，排序函数，最小随机数，最大随机数，重复计算次数（消除随机误差）
    compare_sorting_algorithms(100, int(1e5), 100, slow_sorts, 0, int(5e6), iterations=6)


def test_fast_sorts():
    fast_sorts = {
        "Heap": heap_sort,
        "Shell": shell_sort,
        "Quick": quick_sort,
        "Merge": merge_sort
    }
    # 数据最小长度，最大长度，划分次数，排序函数，最小随机数，最大随机数，重复计算次数（消除随机误差）
    compare_sorting_algorithms(100, int(1e7), 100, fast_sorts, 0, int(5e8), iterations=6)


if __name__ == "__main__":
    #test_slow_sorts()
    test_fast_sorts()
